Find Peak Element (LeetCode 162, Binary Search)

thoughts

• 峰值定義：nums[i] > nums[i-1] && nums[i] > nums[i+1]
• 因為 總有一個峰值存在，可用 Binary Search O(log n)。
• 判斷方向：
  • 如果 nums[mid] < nums[mid+1] → 峰值在右邊
  • 否則 → 峰值在左邊

kotlin

class Solution {
    fun findPeakElement(nums: IntArray): Int {
        var left = 0
        var right = nums.size - 1
        while (left < right) {
            val mid = (left + right) / 2
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }
}

follow up

• 如果有多個峰值，是否要回傳第一個 / 任意一個？
• 如果陣列是循環的 (circular array)，怎麼處理？
• 如果是 2D 矩陣找峰值？（延伸題：LeetCode 1901 Find a Peak Element II）